package com.lw.leetcode.arr.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 1345. 跳跃游戏 IV
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/21 13:39
 */
public class MinJumps {


    public static void main(String[] args) {
        MinJumps test = new MinJumps();
        // [100,-23,-23,404,100,23,23,23,3,404]
//        int[] arr = {100,-23,-23,404,100,23,23,23,3,404};
        int[] arr = {7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8};
        int i = test.minJumps(arr);
        System.out.println(arr.length);
        System.out.println(i);
    }

    public int minJumps(int[] arr) {
        int length = arr.length;
        if (length == 1) {
            return 0;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] flags = new int[length];
        for (int i = 0; i < length; i++) {
            map.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
        }
        Set<Integer> a = new HashSet<>();
        Set<Integer> b = new HashSet<>();
        Set<Integer> ff = new HashSet<>();
        a.add(0);
        int count = 1;
        flags[0] = 1;
        while (true) {
            for (int v : a) {
                if (!ff.contains(arr[v])) {
                    List<Integer> list = map.get(arr[v]);
                    ff.add(arr[v]);
                    for (int c : list) {
                        if (flags[c] == 1) {
                            continue;
                        }
                        if (c == length - 1) {
                            return count;
                        }
                        flags[c] = 1;
                        b.add(c);
                    }
                }
                if (v > 0 && flags[v - 1] == 0) {
                    flags[v - 1] = 1;
                    b.add(v - 1);
                }
                if (v + 1 < length && flags[v + 1] == 0) {
                    if (v + 1 == length - 1) {
                        return count;
                    }
                    flags[v + 1] = 1;
                    b.add(v + 1);
                }
            }
            count++;
            while (!b.isEmpty()) {
                a.clear();
                a.addAll(b);
                b.clear();
            }
            if (a.isEmpty()) {
                break;
            }
        }
        return count;
    }

}
